package drds.plus.sql_process.utils;

import com.google.common.collect.Lists;
import drds.plus.sql_process.abstract_syntax_tree.ObjectCreateFactory;
import drds.plus.sql_process.abstract_syntax_tree.expression.bind_value.BindValue;
import drds.plus.sql_process.abstract_syntax_tree.expression.bind_value.SequenceValue;
import drds.plus.sql_process.abstract_syntax_tree.expression.item.column.Column;
import drds.plus.sql_process.abstract_syntax_tree.expression.item.function.*;
import drds.plus.sql_process.abstract_syntax_tree.node.query.Query;
import drds.plus.sql_process.optimizer.chooser.EmptyResultFilterException;
import drds.plus.sql_process.utils.range.AndRangeProcessor;
import drds.plus.sql_process.utils.range.OrRangeProcessor;

import java.util.*;

/**
 * <pre>
 *  在布尔逻辑中，析取范式(DNF)是逻辑公式的标准化（或规范化），它是合取子句的析取。作为规范形式，它在自动定理证明中有用。
 *  一个逻辑公式被认为是 DNF 的，当且仅当它是一个或多个文字的一个或多个合取的析取。
 *  同合取范式（CNF）一样，在 DNF 中的命题算子是与、或和非。非算子只能用做文字的一部分，这意味着它只能领先于命题变量。
 *  例如，下列公式都是 DNF: AvB 或者 A 或者 (A^B)vC
 * 但如下公式不是 DNF(重点 by czh) : 1.!(AvB)是最外层的算子。2.Av(B^(CvD)) 一个 or 嵌套在一个 and 中
 * 把公式转换成 DNF 要使用逻辑等价，比如双重否定除去、德·摩根定律和分配律。
 * 注意所有逻辑公式都可以转换成析取范式。
 * 但是，在某些情况下转换成 DNF 可能导致公式的指数性爆涨。例如，在 DNF 形式下，如下逻辑公式有 2个项：(XnvYn)^(XnvYn)^(XnvYn)^(XnvYn)...
 * </pre>
 *
 * <pre>
 *     一个命题公式的合取范式可以通过真值表得到，也可以通过等价变换得到。
 *     命题公式还有另一种范式，析取范式。析取范式的定义与合取范式对偶，只要把合取与析取对换就可以由合取项得到析取项，由合取范式得到析取范式。
 * 假设编辑
 * 设A是一个命题公式，A中出现的命题变元为p1，p2，…，pn，以Qi表示pi或┐pi，i=1，…，n。称Q1∧…∧Qn是p1，…，pn的一个合取项，
 * 若干个互不相同的析取项的合取称为一个合取范式，与命题公式A逻辑等价的合取范式称为A的合取范式。
 * （（p∨q）—>r）—>p
 * <=>(┐(p∨q)∨r)—>p （消去第一个—>）
 * <=>┐(┐(p∨q)∨r)∨p （消去第二个—>）
 * <=>┐((┐p∧┐q)∨r)∨p （┐内移）
 * <=>((┐┐p∨┐┐q)∧┐r)∨p （┐内移）
 * <=>（（p∨q)∧┐r)∨p (┐消去）
 * <=>(p∨q∨p)∧(┐r∨p) （∨对∧分配）
 * 这就是所求的原命题公式的合取范式，若再利用交换律和幂等律得：
 * （p∨q∨p)∧(┐r∨p)
 * <=>(p∨q)∧(┐r∨p)
 * 可见，（p∨q）∧(┐r∨p)也是原公式的合取范式，这说明一个命题公式的合取范式不是唯一的。
 * </pre>
 */
/////////////////////////////////////////////////////

/**
 * 下面是tddl里面的注释
 * <p>
 * 用来做一些布尔表达式的转换，比如我们会将(A and B) or C => (A and C) or (A and B)，析取范式便于做计算<br/>
 * 注意，目前处理中不是一个严格的析取范式处理，比如 A and B and C不会进行转化
 *
 * <pre>
 * DNF析取范式:
 *  a. http://zh.wikipedia.org/zh-cn/析取范式
 *  b. http://baike.baidu.com/view/143339.htm
 *
 * 简单析取式: 仅由有限个文字构成的析取式，比如：p,q,p∨q
 * 析取范式：由有限个简单合取式构成的析取式，比如 (p∧q)vr
 * </pre>
 */
public class DnfFilters {
    /**
     * 是否为一简单合取式(只要不是or就行),如果返回false则代表存在or。
     */
    public static boolean isCnf(Filter filter) {
        if (filter == null) {
            return false;
        }
        if (filter.getOperation().equals(Operation.and)) {
            for (Filter subFilter : ((LogicalOperationFilter) filter).getFilterList()) {
                if (!isCnf(subFilter)) {
                    return false;
                }
            }
            return true;
        } else {
            return !filter.getOperation().equals(Operation.or);
        }
    }

    /**
     * 将一个Bool树转换成析取形式 A（B+C）转换为AB+AC。 该方法是将一个filter变成or(and......)...的一个过程
     */
    public static Filter toDnfAndFlat(Filter filter) {
        if (filter == null) {
            return null;
        }
        filter = toDnf(filter);
        filter = dnfFlat(filter);
        return filter;
    }

    /**
     * 将一个Bool树转换成析取形式 A（B+C）转换为AB+AC，不做拉平处理
     */
    public static Filter toDnf(Filter filter) {
        if (filter == null) {
            return null;
        }
        while (!isDnf(filter)) {// 需要都转换为DNF便于做计算
            if (filter.getOperation().equals(Operation.or)) {
                filter = orGradually((LogicalOperationFilter) filter);
            } else if (filter.getOperation().equals(Operation.and)) {
                filter = andSplit((LogicalOperationFilter) filter);
            }
        }
        return filter;
    }

    /**
     * 非严格DNF检查，允许出现 Filter(A and B)
     */
    public static boolean isDnf(Filter filter) {
        if (!isLogicalFilter(filter)) {
            return true;
        }
        if (filter.getOperation().equals(Operation.and)) {
            boolean isAllBooleanFilter = true;
            for (Filter subFilter : ((LogicalOperationFilter) filter).getFilterList()) {
                if (isLogicalFilter(subFilter)) {
                    isAllBooleanFilter = false;
                    break;
                }
            }
            if (isAllBooleanFilter) {// 子集条件不存在and or
                return true;
            }
            for (Filter subFilter : ((LogicalOperationFilter) filter).getFilterList()) {
                if (subFilter.getOperation().equals(Operation.or)) { // 子表达式中存在析取
                    return false;// and的子集条件中不允许or出现
                }
            }
        }
        // 这里可能是and 也可能是or。对子级节点进行遍历
        for (Filter subFilter : ((LogicalOperationFilter) filter).getFilterList()) {
            if (!isDnf(subFilter)) {
                return false;
            }
        }
        return true;
    }

    private static Filter orGradually(LogicalOperationFilter orFilter) {
        for (int i = 0; i < orFilter.getFilterList().size(); i++) {
            orFilter.getFilterList().set(i, toDnf(orFilter.getFilterList().get(i)));
        }
        return orFilter;
    }

    private static Filter andSplit(LogicalOperationFilter andFilter) {
        if (andFilter.getFilterList().size() > 2) {
            throw new IllegalArgumentException("此处不支持And包含超过两个子节点\n" + andFilter);
        }

        if (andFilter.getFilterList().size() == 1) {
            return andFilter;
        }

        if ((!isLogicalFilter(andFilter.getFilterList().get(0))) && (!isLogicalFilter(andFilter.getFilterList().get(1)))) {
            return andFilter;
        }
        andFilter.setLeft(toDnf(andFilter.getLeft()));
        andFilter.setRight(toDnf(andFilter.getRight()));
        // (A+B)C = AC+BC

        boolean leftIsOr = andFilter.getLeft().getOperation().equals(Operation.or);
        boolean rightIsOr = andFilter.getRight().getOperation().equals(Operation.or);
        if (leftIsOr || rightIsOr) {
            Filter orFilter = andFilter.getLeft();
            Filter otherFilter = andFilter.getRight();
            if (rightIsOr) {
                orFilter = andFilter.getRight();
                otherFilter = andFilter.getLeft();
            }

            LogicalOperationFilter leftAndFilter = ObjectCreateFactory.createLogicalOperationFilter();
            leftAndFilter.setOperation(Operation.and);
            LogicalOperationFilter rightAndFilter = ObjectCreateFactory.createLogicalOperationFilter();
            rightAndFilter.setOperation(Operation.and);
            // 构造 AC
            leftAndFilter.setLeft(((LogicalOperationFilter) orFilter).getLeft());
            leftAndFilter.setRight(otherFilter);
            // 构造 BC
            rightAndFilter.setLeft(((LogicalOperationFilter) orFilter).getRight());
            rightAndFilter.setRight(otherFilter);
            // 构造AC + BC
            LogicalOperationFilter newOrFilter = ObjectCreateFactory.createLogicalOperationFilter();
            newOrFilter.setOperation(Operation.or);
            newOrFilter.addFilter(leftAndFilter);
            newOrFilter.addFilter(rightAndFilter);
            return orGradually(newOrFilter);
        }
        return andFilter;
    }

    /**
     * 拉平一个filter树，将多层的嵌套拉平为一层<br/>
     * 比如： A and B and (C and D) => A and B and C and D
     */
    private static Filter dnfFlat(Filter filter) {
        if (!isDnf(filter)) {
            throw new IllegalArgumentException("filter is not dnf!\n" + filter);
        }
        List<List<Filter>> dnfFilterListList = toDnfFilterListList(filter);
        if (dnfFilterListList.size() == 1 && dnfFilterListList.get(0).size() == 1) {
            return dnfFilterListList.get(0).get(0);
        }
        LogicalOperationFilter orFilter = ObjectCreateFactory.createLogicalOperationFilter();
        orFilter.setOperation(Operation.or);
        for (List<Filter> dnfFilterList : dnfFilterListList) {// list list层级是or,list是and
            if (dnfFilterList.size() != 1) {
                LogicalOperationFilter andFilter = ObjectCreateFactory.createLogicalOperationFilter();
                andFilter.setOperation(Operation.and);
                for (Filter dnfFilter : dnfFilterList) {
                    andFilter.addFilter(dnfFilter);
                }
                if (dnfFilterListList.size() == 1) {
                    // 如果只有一个合取，直接返回合取结果
                    return andFilter;
                }
                orFilter.addFilter(andFilter);
            } else {
                orFilter.addFilter(dnfFilterList.get(0));
            }
        }

        return orFilter;
    }

    /**
     * 将一个IFilter全部展开为一个多维数组，会做拉平处理，需要预先调用toDNF/toDNFAndFlat进行预处理转化为DNF范式
     *
     * <pre>
     *  其他节点为list,or节点返回的是listlist(or节点下的子节点filter互相隔离)
     * 比如：(A and B) or (A and C)
     * 返回结果为：
     *   List-
     *      List
     *         -(A , B)
     *      List
     *         -(A , C)
     * </pre>
     */
    public static List<List<Filter>> toDnfFilterListList(Filter filter) {
        if (filter == null || !isDnf(filter)) {
            return Lists.newLinkedList(); // 返回空的数组节点
        }

        List<List<Filter>> dnfFilterListList = new LinkedList();
        if (filter.getOperation().equals(Operation.or)) {
            // or节点返回的是listlist,其他节点为list
            for (int i = 0; i < ((LogicalOperationFilter) filter).getFilterList().size(); i++) {
                dnfFilterListList.addAll(toDnfFilterListList(((LogicalOperationFilter) filter).getFilterList().get(i)));
            }
        } else if (filter.getOperation().equals(Operation.and)) {
            dnfFilterListList.add(toDnfFilterList(filter));// and需要构建dnf
        } else {
            List<Filter> dnfFilterList = new ArrayList<Filter>(1);
            dnfFilterList.add(filter);
            dnfFilterListList.add(dnfFilterList);
        }

        if (dnfFilterListList == null || dnfFilterListList.isEmpty() || dnfFilterListList.get(0) == null || dnfFilterListList.get(0).isEmpty() || dnfFilterListList.get(0).get(0) == null) {
            return new LinkedList<List<Filter>>();
        } else {
            return dnfFilterListList;
        }

    }

    /**
     * 将一个IFilter全部展开为一个平级的数组，不考虑逻辑and/or的组织关系<br/>
     * 需要预先调用toDNF/toDNFAndFlat进行预处理转化为DNF范式
     */
    public static List<Filter> toDnfFilterList(Filter filter) {
        List<Filter> dnfFilterList = Lists.newLinkedList();
        if (filter == null) {
            return dnfFilterList;
        }
        if (!isLogicalFilter(filter)) {// 不是and or
            dnfFilterList.add(filter);
            return dnfFilterList;
        }
        for (int i = 0; i < ((LogicalOperationFilter) filter).getFilterList().size(); i++) {
            if (!isLogicalFilter(((LogicalOperationFilter) filter).getFilterList().get(i))) {
                dnfFilterList.add(((LogicalOperationFilter) filter).getFilterList().get(i));
            } else {
                // 递归处理
                dnfFilterList.addAll(toDnfFilterList(((LogicalOperationFilter) filter).getFilterList().get(i)));
            }
        }
        return dnfFilterList;
    }

    /**
     * 判断是否为and/or的组合节点
     */
    private static boolean isLogicalFilter(Filter filter) {
        return filter instanceof LogicalOperationFilter;

    }

    /**
     * 将析取范式的数组重新构造为一个LogicFilter，使用and/or条件
     */
    public static Filter orDnfFilterListList(List<List<Filter>> dnfFilterListList) {
        if (dnfFilterListList.isEmpty()) {
            return null;
        }
        Filter dnfFilter = andDnfFilterList(dnfFilterListList.get(0));
        for (int i = 1; i < dnfFilterListList.size(); i++) {
            dnfFilter = or(dnfFilter, andDnfFilterList(dnfFilterListList.get(i)));
        }
        return dnfFilter;
    }

    /**
     * 将一系列的boolean filter ，拼装成一个andFilter { boolFilter , boolFilter...} 的filter..
     */
    public static Filter andDnfFilterList(List<Filter> dnfFilterList) {
        if (dnfFilterList == null || dnfFilterList.isEmpty()) {
            return null;
        }
        Filter filter = dnfFilterList.get(0);
        for (int i = 1; i < dnfFilterList.size(); i++) {
            filter = and(filter, dnfFilterList.get(i));
        }
        return filter;
    }

    /**
     * 创建and条件
     */
    public static Filter and(Filter rootFilter, Filter filter) {

        // 相同的就不用合并了
        if (rootFilter == filter) {
            return rootFilter;
        }
        if (filter == null) {
            return rootFilter;
        }

        if (rootFilter == null) {
            rootFilter = filter;
        } else {
            if (rootFilter.getOperation().equals(Operation.and)) {
                ((LogicalOperationFilter) rootFilter).addFilter(filter);
            } else {
                LogicalOperationFilter andFilter = ObjectCreateFactory.createLogicalOperationFilter();
                andFilter.setOperation(Operation.and);
                andFilter.addFilter(rootFilter);
                andFilter.addFilter(filter);
                rootFilter = andFilter;
            }
        }
        return rootFilter;
    }

    /**
     * 创建or条件
     */
    public static Filter or(Filter rootFilter, Filter filter) {

        // 相等的情况下就不合并了
        if (rootFilter == filter) {
            return rootFilter;
        }
        if (filter == null) {
            return rootFilter;
        }

        if (rootFilter == null) {
            rootFilter = filter;
        } else {
            if (rootFilter.getOperation().equals(Operation.or)) {
                ((LogicalOperationFilter) rootFilter).addFilter(filter);
            } else {
                LogicalOperationFilter orFilter = ObjectCreateFactory.createLogicalOperationFilter();
                orFilter.setOperation(Operation.or);
                orFilter.addFilter(rootFilter);
                orFilter.addFilter(filter);
                rootFilter = orFilter;
            }
        }
        return rootFilter;
    }

    /**
     * 将filter中的and/or条件中进行Range合并处理 <br/>
     *
     * <pre>
     * 比如:
     *  a. A =1 And A =2 ，永远false条件，返回EmptyResultFilterException异常
     *  b. (1 < A < 5) or (2 < A < 6)，合并为 (1 < A < 6)
     *  c. A <= 1 or A = 1，永远true条件
     * </pre>
     */
    public static Filter merge(Filter filter) {
        if (filter == null || filter instanceof BooleanFilter) {
            return filter;
        }
        // 先转为dnf结构
        filter = toDnfAndFlat(filter);
        List<List<Filter>> dnfFilterListList = toDnfFilterListList(filter);
        List<List<Filter>> newDnfFilterListList = new LinkedList();
        boolean existGroupFilter = false;
        for (List<Filter> dnfFilterList : dnfFilterListList) {
            List<Filter> newDnfFilterList = new LinkedList();
            for (Filter dnfFilter : dnfFilterList) {
                if (dnfFilter instanceof OrsFilter) {
                    // 出现group，单独计算
                    Filter mergedGroupFilter = groupFilterMerge((OrsFilter) dnfFilter);
                    newDnfFilterList.add(mergedGroupFilter);
                    if (mergedGroupFilter instanceof OrsFilter) {// 如果处理过后还是group
                        existGroupFilter = true;
                    }
                } else {
                    newDnfFilterList.add(dnfFilter);
                }
            }
            newDnfFilterListList.add(newDnfFilterList);
        }

        if (!existGroupFilter) {
            if (!needMerge(newDnfFilterListList)) {
                return filter;
            }
            newDnfFilterListList = mergeOrRepeatFilter(mergeAndRepeatFilter(newDnfFilterListList));
        }

        if (newDnfFilterListList == null || newDnfFilterListList.isEmpty() || newDnfFilterListList.get(0) == null || newDnfFilterListList.get(0).isEmpty() || dnfFilterListList.get(0).get(0) == null) {
            // 返回常量true
            BooleanFilter booleanFilter = ObjectCreateFactory.createBooleanFilter();
            booleanFilter.setOperation(Operation.constant);
            booleanFilter.setColumn("1");
            booleanFilter.setColumnName("1");
            return booleanFilter;
        } else {
            return orDnfFilterListList(newDnfFilterListList);
        }
    }

    /**
     * @param orsFilter 针对or进行处理
     * @return
     * @throws EmptyResultFilterException
     */
    private static Filter groupFilterMerge(OrsFilter orsFilter) {
        if (!needMerge(Arrays.asList(orsFilter.getFilterList()))) {
            return orsFilter;
        }

        List<Filter> filterList = new LinkedList<Filter>();
        OrRangeProcessor orRangeProcessor = new OrRangeProcessor(orsFilter.getColumn());
        for (Filter subFilter : orsFilter.getFilterList()) {
            orRangeProcessor.process(subFilter);
        }
        for (List<Filter> newFilterList : orRangeProcessor.toFilterListList()) {
            for (Filter filter : newFilterList) {
                filterList.add(filter);
            }
        }
        if (filterList.size() > 1) {
            orsFilter.setFilterList(filterList);
            return orsFilter;
        } else if (filterList.size() == 1) {
            return filterList.get(0);
        } else {
            // 返回常量true
            BooleanFilter booleanFilter = ObjectCreateFactory.createBooleanFilter();
            booleanFilter.setOperation(Operation.constant);
            booleanFilter.setColumn("1");
            booleanFilter.setColumnName("1");
            return booleanFilter;
        }
    }

    /**
     * 如果filter中包含函数，或者是绑定变量，则不进行merge
     */
    private static boolean needMerge(List<List<Filter>> dnfFilterListList) {
        for (List<Filter> dnfFilterList : dnfFilterListList) {
            for (Filter dnfFilter : dnfFilterList) {
                if (((BooleanFilter) dnfFilter).getValue() instanceof BindValue//
                        || ((BooleanFilter) dnfFilter).getValue() instanceof SequenceValue//
                        || !isConstantExpressionObject(((BooleanFilter) dnfFilter).getValue())) {//
                    return false;
                }
            }
        }

        return true;
    }

    /**
     * 判断是否为常量的filter
     */
    public static boolean isConstantFilter(BooleanFilter booleanFilter) {
        return isConstantExpressionObject(booleanFilter.getColumn()) && isConstantExpressionObject(booleanFilter.getValue());
    }

    /**
     * 判断是否为常量的表达式对象
     */
    public static boolean isConstantExpressionObject(Object object) {
        if (object instanceof Column || object instanceof Function || object instanceof Query || object instanceof drds.plus.sql_process.abstract_syntax_tree.execute_plan.query.Query) {
            return false;
        }

        if (object instanceof Collection) {
            for (Object object1 : (Collection) object) {
                if (!isConstantExpressionObject(object1)) {
                    return false;
                }
            }
        }

        return true;
    }

    /**
     * 合并析取式中的Or重复条件
     */
    private static List<List<Filter>> mergeOrRepeatFilter(List<List<Filter>> dnfFilterListList) {
        Map<Object, List<Filter>> columnToFilterListMap = new HashMap<Object, List<Filter>>();// 按照列进行分类
        List<List<Filter>> remove = new LinkedList<List<Filter>>();
        for (List<Filter> filterList : dnfFilterListList) {
            if (filterList.size() == 1) { // 只处理单个or条件的表达式，比如 A = 1 or A < 2
                Object column = (((BooleanFilter) filterList.get(0)).getColumn());
                if (!columnToFilterListMap.containsKey(column)) {
                    columnToFilterListMap.put(column, new LinkedList());
                }
                columnToFilterListMap.get(column).add(filterList.get(0));
                remove.add(filterList);
            }
        }
        dnfFilterListList.removeAll(remove); // 先干掉，后面会计算后会重新添加
        for (Object column : columnToFilterListMap.keySet()) {
            OrRangeProcessor orRangeProcessor = new OrRangeProcessor(column);
            for (Filter filter : columnToFilterListMap.get(column)) {
                orRangeProcessor.process(filter);
            }
            if (orRangeProcessor.isFullSet()) {
                return new LinkedList<List<Filter>>();
            } else {
                dnfFilterListList.addAll(orRangeProcessor.toFilterListList());
            }
        }
        return dnfFilterListList;
    }

    /**
     * 合并析取式中的And重复条件
     */
    private static List<List<Filter>> mergeAndRepeatFilter(List<List<Filter>> dnfFilterListList) {
        List<List<Filter>> columnFilterListList = new LinkedList();// 按照列进行分类
        for (List<Filter> filterList : dnfFilterListList) {
            // 每个合取中按照column进行归类
            Map<Comparable, List<Filter>> columnToFilterListMap = new HashMap();
            for (Filter filter : filterList) {
                Comparable column = (Comparable) ((BooleanFilter) filter).getColumn();
                if (!columnToFilterListMap.containsKey(column)) {
                    columnToFilterListMap.put(column, new LinkedList());
                }
                columnToFilterListMap.get(column).add(filter);
            }
            // 针对单个字段的条件进行合并，比如 A > 1 and A < 5 and A > 3合并为 3 < A < 5
            List<Filter> columnFilterList = new LinkedList();
            for (Comparable column : columnToFilterListMap.keySet()) {
                AndRangeProcessor andRangeProcessor = new AndRangeProcessor(column);
                for (Filter filter : columnToFilterListMap.get(column)) {
                    if (!andRangeProcessor.process(filter)) {
                        throw new RuntimeException();
                    }
                }
                List<Filter> boolNodesOfCurrentColumn = andRangeProcessor.toFilterList();
                columnFilterList.addAll(boolNodesOfCurrentColumn);
            }
            columnFilterListList.add(columnFilterList);
        }
        return columnFilterListList;
    }

}
